package code1.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 原题链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 */
public class P17 {

    char[] path;       //用来存放字符的栈
    int top=0;        //栈顶指针
    List<String> result=new ArrayList<>();
    char[][] chs={{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};

    public void backtracking(String digits,int begin){      //begin为digits的下标
        if(top==digits.length()){
            StringBuilder sb=new StringBuilder();
            for(int i=1;i<=top;i++){
                sb.append(path[i]);
            }
            String str = sb.toString();
            if(str!=null && str.length()!=0){
                result.add(sb.toString());
            }
            return;
        }
        int index = digits.charAt(begin) - '2';
        for(int i=0;i<chs[index].length;i++){               //遍历当前数字对应的所有字符
            if(chs[index][i]!=0){
                path[++top]=chs[index][i];
                backtracking(digits,begin+1);       //继续下一个数字
                top--;
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        path=new char[digits.length()+1];
        backtracking(digits,0);
        return result;
    }
}
